#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int x=0;bool f=0;char ch=getchar();
	while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
	while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int Maxn=4005,B=60;
const ll mod=999999999;
ll a[4005][4005],g1[4111/B][4111/B],g2[4111/B][4111],g3[4111][4111/B];

int n,q;

int main(){
	freopen("fire.in","r",stdin);
	freopen("fire.out","w",stdout);
	n=read();q=read();
	while(q--){
		int op=read();
		if(op==1){
			int dir=read(),x=read(),op=read(),w=read();
			if(dir==0){
				if(op==1)for(int i=1;i<=n;i++)g1[x/B][i/B]-=a[x][i],g2[x/B][i]-=a[x][i],g3[x][i/B]-=a[x][i],a[x][i]&=w,g1[x/B][i/B]+=a[x][i],g2[x/B][i]+=a[x][i],g3[x][i/B]+=a[x][i];
				if(op==2)for(int i=1;i<=n;i++)g1[x/B][i/B]-=a[x][i],g2[x/B][i]-=a[x][i],g3[x][i/B]-=a[x][i],a[x][i]|=w,g1[x/B][i/B]+=a[x][i],g2[x/B][i]+=a[x][i],g3[x][i/B]+=a[x][i];
				if(op==3)for(int i=1;i<=n;i++)g1[x/B][i/B]-=a[x][i],g2[x/B][i]-=a[x][i],g3[x][i/B]-=a[x][i],a[x][i]^=w,g1[x/B][i/B]+=a[x][i],g2[x/B][i]+=a[x][i],g3[x][i/B]+=a[x][i];
				if(op==4)for(int i=1;i<=n;i++)g1[x/B][i/B]-=a[x][i],g2[x/B][i]-=a[x][i],g3[x][i/B]-=a[x][i],a[x][i]=(a[x][i]+w)%mod,g1[x/B][i/B]+=a[x][i],g2[x/B][i]+=a[x][i],g3[x][i/B]+=a[x][i];
			}else{
				if(op==1)for(int i=1;i<=n;i++)g1[i/B][x/B]-=a[i][x],g2[i/B][x]-=a[i][x],g3[i][x/B]-=a[i][x],a[i][x]&=w,g1[i/B][x/B]+=a[i][x],g2[i/B][x]+=a[i][x],g3[i][x/B]+=a[i][x];
				if(op==2)for(int i=1;i<=n;i++)g1[i/B][x/B]-=a[i][x],g2[i/B][x]-=a[i][x],g3[i][x/B]-=a[i][x],a[i][x]|=w,g1[i/B][x/B]+=a[i][x],g2[i/B][x]+=a[i][x],g3[i][x/B]+=a[i][x];
				if(op==3)for(int i=1;i<=n;i++)g1[i/B][x/B]-=a[i][x],g2[i/B][x]-=a[i][x],g3[i][x/B]-=a[i][x],a[i][x]^=w,g1[i/B][x/B]+=a[i][x],g2[i/B][x]+=a[i][x],g3[i][x/B]+=a[i][x];
				if(op==4)for(int i=1;i<=n;i++)g1[i/B][x/B]-=a[i][x],g2[i/B][x]-=a[i][x],g3[i][x/B]-=a[i][x],a[i][x]=(a[i][x]+w)%mod,g1[i/B][x/B]+=a[i][x],g2[i/B][x]+=a[i][x],g3[i][x/B]+=a[i][x];
			}
		}else{
			int p=read(),q=read();
			ll ans=0;
			int now=0,now1=0;
			while(now*B+B-1<=p){
				now1=0;while(now1*B+B-1<=q)ans+=g1[now][now1],now1++;
				for(int i=now1*B;i<=q;i++)ans+=g2[now][i];
				now++;
			}
			for(int j=now*B;j<=p;j++){
				now1=0;while(now1*B+B-1<=q)ans+=g3[j][now1],now1++;
				for(int i=now1*B;i<=q;i++)ans+=a[j][i];
			}printf("%lld\n",ans);
		}
	}
	return 0;
}
/*
4 8
1 0 2 3 5
1 1 3 4 2
2 3 4
1 1 4 2 6
1 0 1 4 7
2 4 4
1 1 2 1 3
2 2 2
*/
